package com.topcoder.srm518;

import java.util.Arrays;

public class ConvexSequence {
	// brutal force
	public long getMinimum(int[] a) {
		long result = 0;
		while (true) {
			long lastResult = result;
			for (int i = 1; i < a.length - 1; i++) {
				int delta = Math.max(0, (-a[i - 1] - a[i + 1] + 2 * a[i] + 1) / 2);
				a[i] -= delta;
				result += delta;
			}
			if (lastResult == result) return result;
		}
	}
	
	// binary search
	public long getMinimum2(int[] a) {
		int N = a.length;
		long count = 0;
		int[] b = Arrays.copyOf(a, N);
		
		for (int i=1; i<N; i++) {
			int hi = a[i];
			int lo = 0;
			
			if (!test(hi, i, a, b)) {
				while (hi > lo + 1) {
					int mid = (hi + lo) / 2;
					if (test(mid, i, a, b)) {
						lo = mid;
					}
					else {
						hi = mid;
					}
				}
				count += a[i] - lo;
				a[i] = lo;
				b[i] = lo;
			}
		}
		
		return count;
	}
	
	private boolean test(int R, int p, int[] a, int[] b) {
		b[p] = R;
		for (int i=p+1; i<a.length; i++) {
			b[i] = Math.max(2*b[i-1] - b[i-2], 0);
			if (b[i] > a[i]) return false;
		}
		return true;
	}
}
